Typically, routers have a route processor which communicates with other routers in a network to obtain updates of route information regarding the network. A route processor maintains a routing table which contains a large number of entries or elements for use by the router to determine how to forward packets that are received by the router. Conventional routing tables may contain hundreds of thousands of routing entries or elements, and as a greater number of devices such as personal data assistants (PDAs), cell phones, and other devices are assigned IP addresses, the number of entries in routing tables is expected to grow substantially over the coming years.
In the Internet, a routing protocol known as Border Gateway Protocol (BGP) provides a way for routers to share routing information with other routers throughout the network. These other routers that a router speaks to are called “BGP peers.” FIG. 1 illustrates an example of a BGP speaking router 20 in communications with three BGP peers (routers) 22, 24, 26 shown as Peer 1, Peer 2 and Peer 3 in this example. As the router 20 learns new routing information, it may need to communicate this new information to one or more of its peers 22, 24, 26.
FIG. 2 shows one method to track a transmission status of data elements 30, such as routing entries (shown as I1 to I4), with respect to peers 32 (i.e., which peers need to be updated with particular data elements). In FIG. 2, data elements I1-I4 are shown as column headers, and Peers 1-3 are shown as row headers. Such a table data structure 34 can be used in a router to track which peers need to be updated with what data elements. For example in FIG. 2, data elements I1 and I4 need to be communicated to Peer 1, data elements I2 and I4 need to be communicated to Peer 2, and data elements I1 and I4 need to be communicated to Peer 3, in this example.
As recognized by the present inventors, such a table data structure 34 to track the status of data elements 30 as shown in FIG. 2 is undesirable because it requires large amounts of memory to form this data structure. This is particularly true where the number of data elements 30 may be on the order of hundreds of thousands of routing entries or data elements, such as in the case of route entries in a routing table of a router which are to be communicated to numerous peers in the network.
As recognized by the present inventors, what is needed is a method for tracking the state or transmission status of data elements with respect to peers or other devices or other entities in a network.
It is against this background that various embodiments of the present invention were developed.